﻿class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        if (head == nullptr || head->next == nullptr)
            return nullptr;
        while (fast && fast->next)
        {

            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                break;

        }//找到相遇点
        if (fast == nullptr || fast->next == nullptr)
            return nullptr;
        ListNode* ptr = head;
        while (ptr != slow)
        {
            ptr = ptr->next;
            slow = slow->next;
        }
        return ptr;
    }
};
//题目：要求找到链表中的环的入口点
//使用快慢指针进行操作
//我们可以从数学角度进行分析一下
//对这些数据假设一下。
//快指针：一次移动两个节点
//慢指针：一次移动一个节点
//且，在环中，快慢指针最后一定会相遇，假设在距入环点 b 个节点的位置处相遇，
//快指针移动了 a+n*(b+c)+b个节点
//慢指针移动了 a+b 个节点
//且快指针移动的节点数是慢指针移动的节点数的两倍
//可以建立等式
//2*(a+b) = a+n*(b+c)+b
//消除一定的同类项
//可得到
//a=(n-1)*(b+c)+c
//所以可以得到
//从相遇点移动(n−1)个环，再移动剩下的c个节点，等于从链表开头移动到环入口的节点数。
//所以，我们可以使用两个指针一次移动一个节点分别从链表开头遍历与从相遇点移动，最火相遇时，就是环的入口节点。